package com.leetcode.partition6;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/29 8:44
 */
public class LC517超级洗衣机 {

    public static int findMinMoves(int[] machines) {
        return solution(machines);
    }

    private static int solution(int[] machines) {
        int sum = 0, avg, answer = Integer.MIN_VALUE;
        for (int i = 0; i < machines.length; i++) sum += machines[i];
        if (sum % machines.length != 0) return -1;
        avg = sum / machines.length;        //每个洗衣机需要的衣服数
        int[] diff = new int[machines.length];   //最终状态
        //将machines与machinesEnd每位分别作差，即可求出每台洗衣机需要的衣服数或者多余的衣服数
        for (int i = 0; i < machines.length; i++) {
            diff[i] = machines[i] - avg;
        }
        // 遍历diff，负数表示该洗衣机需要的衣服数，正数表示多余的衣服数；而相邻的洗衣机衣服可以户给，
        // 因此在遍历的过程中，将当前所需的衣服数加给相邻洗衣机
        for (int i = 0; i < diff.length - 1; i++) {
            //最终答案由在变化的过程中，machinesEnd最大的绝对值决定
            answer = Math.max(answer, Math.max(diff[i + 1], Math.abs(diff[i])));
            diff[i + 1] += diff[i];       //将当前位置的洗衣机多余或者缺少的衣服分发给相邻或向相邻洗衣机索取
        }
        System.out.println(Arrays.toString(diff));
        return Math.max(answer, diff[diff.length - 1]);
    }

    public static void main(String[] args) {
        int[] machines = {9, 1, 8, 8, 9};
        System.out.println(findMinMoves(machines));
    }
}
